import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
//滑动窗口最大值
/*用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
*/

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {//k是窗口大小
        ArrayDeque<Integer> deque = new ArrayDeque<>();//ArrayDeque才是Deque的实现类
        int n = nums.length;
        int[] res = new int[n - k + 1];//记录结果的数组，这个数组存储的是元素下标
        int idx = 0;//结果数组的下标
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出，i表示的是窗口最后一个元素的位置
            while(!deque.isEmpty() && deque.peekFirst() < i - k + 1){//如果头部的下标小于i-k+1，就将队头元素移除
                deque.pollFirst();
            }

            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {//如果尾部的元素小于当前元素，将对应的元素移除
                deque.pollLast();
            }

            deque.offerLast(i);//插入下标i

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){//当i满足子串长度时，就开始可以有答案了
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}
public class slidingWindowMaximum {
    public static void main(String[] args) {
        int[] a = {1,3,-1,-3,5,3,6,7};//初始矩阵
        int length = 3;//表示窗口大小
        var main = new slidingWindowMaximum();
        var c = new Solution();
        int[] res = c.maxSlidingWindow(a,2);
        System.out.println(Arrays.toString(res));
    }
}
